1. Technical Field
The present invention relates to user authentication. More specifically, the present invention relates to user authentication in various digital devices, systems and networks.
2. Description of the Prior Art
Cryptosystems use crypto keys for cryptographic computation. In the cryptosystems based on asymmetric cryptography such as RSA (Rivest, Shamir, and Adleman), crypto keys are generated in pairs of a public key and a private key. The way of using the public/private key pair defines two applications. One application uses the private key as a signature key to produce a digital signature on a digital message and the public key as a verification key for verifying whether a value is a valid digital signature. The other application uses the public key as an encryption key to encrypt a plaintext into a cipher and the private key as a decryption key to decrypt the cipher back to the plaintext.
Users who are a signatory performing digital signature must keep their signature private key confidential. Also, users who are a cipher receiver must keep their decryption private key confidential. The private key is a secret. Disclosure of the public key must not reveal the secrecy of the private key, though the private key has a dependence on the public key. Due to this secrecy requirement, computational intractability of deriving the private key from the public key is vital to the security of asymmetric cryptosystems.
In the RSA scheme, computation is carried out with modular arithmetic using the product of two primes as the modulus. The computational intractability of deriving the private key from the pairing public key rests in part on the lack of an efficient algorithm for factoring the product back to the two primes. Nevertheless, the private key is not independent of the public key because of their relationship with the two secret primes. This relationship prohibits the private key from being chosen by a user at the discretion of the user. This relationship also imposes that the private key cannot be replaced except by resorting to a regeneration of the public/private key pair.
The RSA cryptosystem is described in U.S. Pat. No. 4,405,823 and in the paper: Rivest, Shamir, and Adleman, “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems,” Communications of the ACM, vol. 21 (1978), pp. 120-126. Several standards have been developed for teaching this asymmetric cryptography, including PKCS #1: RSA Cryptography Standard, November 1993 (v. 1.5) & June 2002 (v. 2.1) and IEEE Std 1363-2000: IEEE Standard Specification for Public-Key Cryptography, which are respectively available at the web site of RSA Laboratories and that of IEEE. These standards include descriptions on key generation, encryption, decryption, signature generation, signature verification, and other related techniques.
RSA computations always involve modular arithmetic. The definition on modular arithmetic is given here. If x and y are integers, then x is said to be congruent to y modulo a positive integer z, written x≡y (mod z), if z divides (x−y). The positive integer z is called the modulus of the congruence.
The RSA key generation process recommended in PKCS #1 v. 1.5 is summarized below:
(1) A positive integer e is chosen as the public exponent.
(2) Two distinct odd primes p and q are randomly selected such that e is relatively prime to both p−1 and q−1.
(3) The public modulus is the product n=p×q.
(4) The private exponent d is chosen such that both p−1 and q−1 divide d×e−1.
The RSA public exponent e and modulus n are used to encrypt a plaintext integer m, assumed less than n, to get a cipher integer c by computing c≡me (mod n). The private exponent d and modulus n are used to decrypt the cipher c back to the plaintext m by computing m≡cd (mod n).
In certain cryptosystems such as those built accordingly to the SSL/TLS (Secure Sockets Layer/Transport Layer Security) protocols, encryption with RSA is often combined with encryption using symmetric cryptography, creating a hybrid cryptosystem. In such a hybrid cryptosystem, one side of the communication encrypts a randomly generated secret with a RSA public key while the other side receives and decrypts the encrypted secret with a pairing RSA private key; subsequently, both sides use the same secret as a symmetric crypto key for confidential communications. The symmetric crypto key exchanged in this way is called a session key. For details, refer to RFC 2246 and other related documents at the web site of Internet Engineering Task Force.
The RSA private exponent d and modulus n are used to produce a digital signature. First, a digital message M is processed by a selected collision-resistant hash function to produce a digest on M, expressed as hash(M). Next, the digital signature on M, expressed as signature(M), is obtained by computing signature(M)≡hash(M)d (mod n).
The RSA public exponent e and modulus n are used to validate a value as being a valid digital signature. Suppose that M∥SGN is received by a verifier, where M represents a digital message and SGN represents a value that is attached as a digital signature on M. The verifier first computes hash(M) using the selected collision-resistant hash function, and decrypts SGN with the public key (n, e) by computing SGNe (mod n); next, the verifier compares hash(M) with the decryption result. If the comparison yields an equal, then SGN is a valid digital signature.
Hash functions are used in producing a digital signature. Hash functions are deterministic, meaning that the output is completely determined by the input. The hash function used in digital signature should generally be collision-resistant. This means that it is infeasible to find two distinct inputs that could produce the same output of the hash function. Collision-resistant hash functions also have the desired property of being one-way; this means that given an output, it is infeasible to find an input whose hash is the specified output. In addition, the hash function should be a mask generation function with pseudorandom output: Given one part of the output but not the input, it should be infeasible to predict another part of the output. Six hash functions possessing these properties are suggested for various implementations in PKCS #1 v. 2.1: MD2, MD5, SHA-1, SHA-256, SHA-384, and SHA-512.
Application of asymmetric cryptography raises a concern. How can a public-key's user know that the public key in use is authentic? A cheater may cheat the user into validating a false digital signature as valid with a fictitious public key. Public-key certificates, also known as digital certificates, provide a solution.
Abstractly, a public-key certificate consists of three main components: a public key, an entity's identifier, and a certification authority's digital signature. Thus, a public-key certificate provides a binding between a public key and an identification of an entity and ensures that the public key belongs to the identified entity and that the entity possesses the pairing private key. By validating the certification authority's digital signature, users of the public key prove this binding. A certification authority, abbreviated as CA, is a trusted party who certifies and issues public-key certificates. Revoking certain certificates and publishing the revoked certificates are also part of a CA's duties.
Asymmetric cryptosystems have been around for a long time, but have not been as widely applied as perceived. For example, user login with password where no public/private key pairs are used remains common. One reason is that the infrastructure of ensuring a certificate being valid is cumbersome to build and operate. The task becomes more complicated due to the inflexibility of changing the secret private key. Thus, there exists a need to alleviate the complication.
In certain circumstances, a digital message may need to be signed by several signatories and then verified by one verifier alone. Multisignature techniques were invented to meet the need. See Colin Boyd, “Digital Multisignatures,” in Cryptography and Coding (H. J. Becker and F. C. Piper Eds.), Oxford University Press, 1989, pp. 241-246. In U.S. Pat. No. 6,209,091, two multisignature systems are described: (1) a multiplicative scheme with sequential partial signing, and (2) an additive scheme with asynchronous partial signing. These and other related works result in an advantage. The private key is not needed for the signature computation because the digital signature is computed from a plurality of partial signatures, each of which is computed, respectively, from the digital message and a signature subkey. The private key never exists after the signature subkeys have been derived from it. Therefore, the secrecy of the private key is well protected.
Extended from the multisignature techniques, split-private-key cryptosystems were invented and developed by Ravi Ganesan and others. See U.S. Pat. Nos. 5,535,276, 5,557,678, 5,905,799, etc., where the private exponent key is divided into a first private key portion and a second private key portion. With the two private key portions, asymmetric cryptosystems have at least two benefits. Firstly, dividing the secret into two portions and separately safeguarding each portion strengthens the protection for the secrecy of the private key. Secondly, the user is allowed to use a short secret key while the underlying cryptosystem uses a long but secure private key. The first benefit is conventional wisdom on protecting secrecy. The second benefit is significant, in part because attacks on short RSA secret exponents are feasible as discovered by M. J. Wiener in “Cryptanalysis of Short RSA Secret Exponents, IEEE Trans. on Information Theory, May, 1990, vol. 36, no. 3, pp. 553-558.” Recent cryptanalysis on short RSA private exponents includes a technique discovered by Dan Boneh and Glenn Durfee in “Cryptanalysis of RSA with Private Key d Less Than N0.292, IEEE Trans. on Information Theory, July, 2000, vol. 46, no. 4, pp. 1339-1349.”
The multisignature and split-private-key techniques add values to the RSA theory on the aspects of security and user convenience. The inflexibility of changing the private secret remains unresolved, however. In order to change the private key portions, users may resort to either one of two ways: the first by which the original private key is recovered from the two portions and then divided again and the second by which a new public/private key pair is generated and subsequently the new private key is divided.
However, it is undesirable to recover the original private key because this action contradicts the principle of separating the secrecy and requires special measures to protect the secrecy from disclosure during the recovery process. Regenerating a public/private key pair should also be avoided because such a task is more complicated than generating a first-time public/private key pair due to the added effort of revoking the replaced public-key certificate.
Therefore, there remains a need to improve the split private key techniques on the aspect of changing the private key portions in a more efficient and flexible manner.
Digital signature techniques can be applied to user authentication. Suppose that a user at a user station requests a system station for login. The system station returns a random message as a challenge to the user station. Next, the user station computes a digital signature on the challenge message as a response. The system station grants permission to the user when it validates the response being a valid digital signature. Specification about this process can be found in “ISO/IEC 9798-3: 1998, Information technology—Security techniques—Entity authentication—Part 3: Mechanisms using digital signature techniques.”
This login process has one advantage. Disclosure of the public key, which is used by the system station for validating the response, does not reveal the secrecy of the user's private key, provided that the public/private key pair is generated according to the security requirement. The private key is a computer-generated secret and not a secret chosen by a human user. Therefore, the private key is often kept in a physical token like an IC card and accessible via a user PIN (Personal Identification Number). Implementation of this technique requires additional hardware cost, because it demands the use of IC cards as well as card readers and other equipment such as card manufacturing equipment. Moreover, new cryptanalysis techniques to crack the private key inside the IC card have been discovered, including time analysis and fault analysis attacks.
In contrast, popular login processes, including those implemented in UNIX-like systems, use password and symmetric cryptography. One exemplary process is the following. The system station keeps an authentication database in which each legitimate user has registered identification data together with a hash digest of the user's password. At a user station, a user requests a login and enters his identification and password. The password entry is then run through the same hash function to produce a new hash digest. The resulting hash and the password entry are not sent to the accessed system. Instead, the accessed system creates a random message as a challenge, which is used to challenge the user station to prove that the new hash is produced from the valid password. The challenge is sent to the user station. The user station enciphers the received challenge with the new hash digest as the encryption key to produce a response. Next, the accessed system deciphers the received response with a decryption key, which is the stored hash digest associated with the claimed identity, to obtain a result. The user login succeeds if the result matches the challenge.
User authentication with password as described has been widely practiced despite several vulnerabilities. One threat to password safety arises from stealing passwords (and identifications) by Trojan horses. A Trojan horse is an intrusive programming code planted in a computer by attackers. The instructions of a Trojan horse are hidden and can do damage, while the intruded computer may appear to function normally. One type of Trojan horse can secretly record keyboard entries and then send the records to an outside computer, thereby stealing confidential information.
Passwords are also vulnerable to dictionary attacks. Among various forms of dictionary attacks that have been reported, the global dictionary attack is one that is hard to defeat. Attackers try a password guess globally, i.e. try every guess on all user accounts. Attackers can carry out an off-line global dictionary attack when the authentication database is available. Such an attack is very likely to succeed, because ordinary users often choose weak passwords easy to remember but can be included in a dictionary as high-prioritized guesses by an attacker. On-line global dictionary attacks are another form of dictionary attack, where the global guess is tried on-line. On-line attacks on one user account are often less likely to succeed if a throttling mechanism is built in the accessed system to restrict the number of attempts. But on-line global dictionary attacks may be able to bypass the throttling, because the guess attempts are globally applied to all accounts and not separately applied to one user account. As a further threat, on-line global dictionary attacks may cause the accessed system to deny services requested by legitimate users.
Another type of dictionary attack, called encryption dictionary attack, is described below. An eavesdropper may steal a pair of challenge and response messages. As defined, the response is computed by enciphering the challenge using the hash digest of a password entry as the encryption key. Consequently, this attacker can guess the password, off-line, by enciphering the challenge with hash(PWD) as the encryption key and comparing the cipher with the response, where PWD is a guess on the password. This type of dictionary attack is threatening.
Moreover, it is possible that attackers could build their own version of the login software that would accept a hash digest rather than a password entry as input. With this software, logins become easy when correct hash digests are available to the attackers.
Because user authentication with password may prevail for a long time, there exists a need to defeat these known attacks while allowing users to login with password as they are used to.